import heapq
import math
from heapq import *
from typing import *


def solution_iq_17_06(n: int) -> int:
    s = str(n)
    length = len(s)
    dp = [[-1] * length for _ in range(length)]

    def f(i, j, limit):
        if i == length:
            return j
        if not limit and dp[i][j] != -1:
            return dp[i][j]
        res = 0
        up = int(s[i]) if limit else 9
        for d in range(up + 1):
            res += f(i + 1, j + (d == 2), limit and d == up)
        if not limit:
            dp[i][j] = res
        return res

    return f(0, 0, True)


def solution_lcp_24(nums: List[int]) -> List[int]:
    MOD = 10 ** 9 + 7
    ans = [0] * len(nums)
    # python默认小根堆，因此left中值取反
    left = []
    right = []
    left_sum = right_sum = 0
    for i, b in enumerate(nums):
        b -= i
        if i % 2 == 0:  # 包含i的前缀长度为奇数 [0,...,i]
            if left:
                # 如果b比left的最大值大，那么插入到right中去
                # 否则插入到left中
                # 此处left_sum值已经删除了left的堆顶，并加入b
                left_sum -= max(-left[0] - b, 0)
            # 无论插入那边，都可以用这个函数
            t = -heappushpop(left, -b)
            heappush(right, t)
            right_sum += t
            # 现在
            ans[i] = (right_sum - right[0] - left_sum) % MOD
        else:  # 前缀长度为偶数,left必定比right少1,往left里插入
            right_sum += max(b - right[0], 0)
            t = heappushpop(right, b)
            left_sum += t
            heappush(left, -t)
            ans[i] = (right_sum - left_sum) % MOD
    return ans


def solution_lcp_30(nums: List[int]) -> int:
    heap = []
    cnt = 0
    cur = 1
    if sum(nums) < 0:
        return -1
    for num in nums:
        if num < 0:
            heapq.heappush(heap, num)
        cur += num
        while heap and cur <= 0:
            tmp = heapq.heappop(heap)
            cur -= tmp
            nums.append(tmp)
            cnt += 1
        # 如果cur<=0,当前num一定为负，heap一定不为空
        # 弹出最大的一定能使得cur为正
        # 不需要加到最后
        # 一定有结果
        # if cur <= 0:
        #     cur -= heapq.heappop(heap)
        #     cnt += 1
    return cnt


def solution_lcp_61(temperatureA: List[int], temperatureB: List[int]) -> int:
    n = len(temperatureA)
    d = [0] * (n - 1)
    for i in range(n - 1):
        ta = temperatureA[i] - temperatureA[i + 1]
        tb = temperatureB[i] - temperatureB[i + 1]
        if ta != tb and ta * tb == 0 or ta * tb < 0:
            d[i] = 1
        else:
            d[i] = 0
    left = 0
    right = 0
    ans = 0
    while right < n - 1:
        if d[right] == 1:
            ans = max(ans, right - left)
            right += 1
            while right < n - 1 and d[right] == 1:
                right += 1
            left = right
            if right >= n - 1:
                break
        right += 1
    return max(ans, right - left)


def solution_lcp_51(materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:
    n = len(cookbooks)
    m = len(materials)
    path = [([0] * m, 0, 0)]
    ans = -1

    def dfs(i):
        nonlocal ans
        if i == n:
            return
        # 不选
        dfs(i + 1)
        # 选
        tmp = path[-1][0][:]
        for j in range(m):
            tmp[j] += cookbooks[i][j]
            if tmp[j] > materials[j]:
                return
        path.append((tmp, path[-1][1] + attribute[i][0], path[-1][2] + attribute[i][1]))
        if path[-1][2] >= limit:
            ans = max(ans, path[-1][1])
        dfs(i + 1)
        path.pop()

    dfs(0)
    return ans


def solution_lcr_107_01(mat: List[List[int]]) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    dp = [[-1] * n for _ in range(m)]
    for i, row in enumerate(mat):
        for j, x in enumerate(row):
            if x == 0:
                dp[i][j] = 0
    for i in range(m):
        for j in range(n):
            if dp[i][j] == 0:
                continue
            mn = math.inf
            if i > 0:
                mn = min(mn, dp[i - 1][j] + 1)
            if j > 0:
                mn = min(mn, dp[i][j - 1] + 1)
            dp[i][j] = mn
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            if dp[i][j] == 0:
                continue
            mn = dp[i][j]
            if i < m - 1:
                mn = min(mn, dp[i + 1][j] + 1)
            if j < n - 1:
                mn = min(mn, dp[i][j + 1] + 1)
            dp[i][j] = mn
    return dp


def solution_lcp_40(cards: List[int], cnt: int) -> int:
    # heapify(cards)
    # odd, even = [], []
    # while cards:
    #     t = heappop(cards)
    #     if t % 2:
    #         odd.append(t)
    #     else:
    #         even.append(t)
    # ans, idxo, idxe = 0, len(odd) - 1, len(even) - 1
    # if cnt % 2:
    #     if idxe >= 0:
    #         ans += even[idxe]
    #         idxe -= 1
    #     else:
    #         return 0
    #     cnt -= 1
    # while cnt > 0:
    #     if idxo >= 1 and idxe >= 1:
    #         if odd[idxo] + odd[idxo - 1] > even[idxe] + even[idxe - 1]:
    #             ans += odd[idxo] + odd[idxo - 1]
    #             idxo -= 2
    #         else:
    #             ans += even[idxe] + even[idxe - 1]
    #             idxe -= 2
    #     elif idxo >= 1:
    #         ans += odd[idxo] + odd[idxo - 1]
    #         idxo -= 2
    #     elif idxe >= 1:
    #         ans += even[idxe] + even[idxe - 1]
    #         idxe -= 2
    #     else:
    #         return 0
    #     cnt -= 2
    # return ans
    cards.sort(reverse=True)
    s = sum(cards[:cnt])
    if s % 2 == 0:
        return s

    def replace_sum(x: int) -> int:
        for v in cards[cnt:]:
            if v % 2 != x % 2:
                return s - x + v
        return 0

    x = cards[cnt - 1]
    ans = replace_sum(x)
    for v in cards[cnt - 1::-1]:
        if v % 2 != x % 2:  # 检查另一种替换的可能
            ans = max(ans, replace_sum(v))
            break
    return ans